<html>
<head><meta charset="utf-8"><title>Different access to slice length · t-compiler/wg-mir-opt · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/index.html">t-compiler/wg-mir-opt</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html">Different access to slice length</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="242818544"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242818544" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242818544">(Jun 16 2021 at 00:59)</a>:</h4>
<p>I was experimenting with range based analysis in MIR, but before it wanted to try an optimization to remove bound checks for slice accesses on MIR level. I use a function like</p>
<div class="codehilite"><pre><span></span><code>pub fn bound(index: usize, slice: &amp;[u8]) -&gt; u8 {
    if index &lt; slice.len() {
        slice[index]
    } else {
        42
    }
}
</code></pre></div>
<p>and hope to see a bound check optimized away. So far mir-opt-level = 3 doesn't provide such guarantees, it mainly inlines a call to <code>slice.len()</code> and that's it.</p>
<p>But my question has another nature. I see that in bound check length is calculated as (ignore the local indexes for now)</p>
<div class="codehilite"><pre><span></span><code>        _8 = Len((*_2));
        _9 = Lt(_7, _8);
        assert(move _9, &quot;index out of bounds: the length is {} but the index is {}&quot;, move _8, _7) -&gt; bb3;
</code></pre></div>
<p>while in a "normal" code it's like for <code>slice.len()</code>:</p>
<div class="codehilite"><pre><span></span><code>        _6 = &amp;(*_2);
        _5 = core::slice::&lt;impl [u8]&gt;::len(move _6) -&gt; bb1;
</code></pre></div>
<p>Is there a reason for such divergence? I've made an optimization pass that does the following</p>
<div class="codehilite"><pre><span></span><code>-         _6 = &amp;(*_2);                     // scope 0 at $DIR/basic_range.rs:23:17: 23:22
-         _5 = core::slice::&lt;impl [u8]&gt;::len(move _6) -&gt; bb1; // scope 0 at $DIR/basic_range.rs:23:17: 23:28
-                                          // mir::Constant
-                                          // + span: $DIR/basic_range.rs:23:23: 23:26
-                                          // + literal: Const { ty: for&lt;&#39;r&gt; fn(&amp;&#39;r [u8]) -&gt; usize {core::slice::&lt;impl [u8]&gt;::len}, val: Value(Scalar(&lt;ZST&gt;)) }
+         nop;                             // scope 0 at $DIR/basic_range.rs:23:17: 23:22
+         _5 = Len((*_2));                 // scope 0 at $DIR/basic_range.rs:23:17: 23:28
+         goto -&gt; bb1;                     // scope 0 at $DIR/basic_range.rs:23:17: 23:28
</code></pre></div>
<p>with a hope to either see it useful to other optimization passes (not yet tested) or to use in my attempt to remove bound checks as it's much more convenient to have similar form of statements. Is this worth it and is it sound?</p>



<a name="242831923"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242831923" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242831923">(Jun 16 2021 at 05:37)</a>:</h4>
<blockquote>
<p>Is this worth it </p>
</blockquote>
<p>yes, though ideally we'd have some way to first inline len and then recognize that the len rvalue is the same as transmute and field access</p>
<blockquote>
<p>and is it sound?</p>
</blockquote>
<p>depends on how you are checking this</p>



<a name="242832251"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242832251" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242832251">(Jun 16 2021 at 05:44)</a>:</h4>
<p>We could plausibly have a pass, not unlike intrinsic lowering, that looks for <code>[T]::len</code> explicitly, right?</p>



<a name="242832458"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242832458" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242832458">(Jun 16 2021 at 05:49)</a>:</h4>
<p><span class="user-mention silent" data-user-id="125270">scottmcm</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Different.20access.20to.20slice.20length/near/242832251">said</a>:</p>
<blockquote>
<p>We could plausibly have a pass, not unlike intrinsic lowering, that looks for <code>[T]::len</code> explicitly, right?</p>
</blockquote>
<p>I'm assuming this is how <span class="user-mention" data-user-id="420832">@Alex Vlasov</span> did it? slice is a lang item, so looking up the len method on that is not problematic</p>



<a name="242848966"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242848966" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242848966">(Jun 16 2021 at 08:53)</a>:</h4>
<p>Yes, I do look for a call to core::slice::len, take the argument and remove go backwards in boby.block.statements to remove one that takes a borrow and instead add a Len operation and modify the terminator</p>



<a name="242850065"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242850065" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242850065">(Jun 16 2021 at 09:00)</a>:</h4>
<p>Separately I would appreciate some guidance on how to properly get a function name. So far I had to format a TyS structure and string match it, and could not find a way to do it properly (my deepest point was FnDef(def_id, …)). In a similar manner I would likely to improve heuristics and be able to get type information of the parameter going into the len() to ensure that it’s a slice and when I work backwards to remove the borrow to may be (not sure though it’s possible) get the type of my manipulations to ensure that I pass [T] to Len statement</p>



<a name="242851146"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242851146" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242851146">(Jun 16 2021 at 09:07)</a>:</h4>
<p>As for “why” I want to do it is that I have a draft of the pass that recognizes (yet separately) casts like bool as u8 and then allow to modify SwitchInt for such cases and remove impossible branches, and also follows through the (unsigned) integer related statements and keeps range information and relations like &lt; along with the control flow information, like “if we did jump to bb1 then a &lt; b”, so it was natural to start and make it niche for bound checks elimination</p>



<a name="242858683"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242858683" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242858683">(Jun 16 2021 at 10:01)</a>:</h4>
<p><span class="user-mention silent" data-user-id="420832">Alex Vlasov</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Different.20access.20to.20slice.20length/near/242851146">said</a>:</p>
<blockquote>
<p>As for “why” I want to do it is that I have a draft of the pass that recognizes (yet separately) casts like bool as u8 and then allow to modify SwitchInt for such cases and remove impossible branches, and also follows through the (unsigned) integer related statements and keeps range information and relations like &lt; along with the control flow information, like “if we did jump to bb1 then a &lt; b”, so it was natural to start and make it niche for bound checks elimination</p>
</blockquote>
<p>side note: make sure to use the dataflow systems for this, it will safe you a lot of work you'd be doing manually</p>



<a name="242858719"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242858719" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242858719">(Jun 16 2021 at 10:01)</a>:</h4>
<p><span class="user-mention silent" data-user-id="420832">Alex Vlasov</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Different.20access.20to.20slice.20length/near/242850065">said</a>:</p>
<blockquote>
<p>Separately I would appreciate some guidance on how to properly get a function name. So far I had to format a TyS structure and string match it, and could not find a way to do it properly (my deepest point was FnDef(def_id, …)). In a similar manner I would likely to improve heuristics and be able to get type information of the parameter going into the len() to ensure that it’s a slice and when I work backwards to remove the borrow to may be (not sure though it’s possible) get the type of my manipulations to ensure that I pass [T] to Len statement</p>
</blockquote>
<p>you mean, how to find exactly the [T]::len function and nothing else?</p>



<a name="242858839"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242858839" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242858839">(Jun 16 2021 at 10:02)</a>:</h4>
<p>if that's what you're asking, you should be using <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/lang_items/struct.LanguageItems.html#method.slice_impl">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/lang_items/struct.LanguageItems.html#method.slice_impl</a> to get the right impl, then find the len function via <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.associated_items">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.associated_items</a> and <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/assoc/struct.AssocItems.html#method.filter_by_name">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/assoc/struct.AssocItems.html#method.filter_by_name</a></p>



<a name="242860462"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242860462" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242860462">(Jun 16 2021 at 10:20)</a>:</h4>
<p>Hm, I can not connect the dots. When I do traverse the block terminators I end up with <code>TerminatorKind::Call { func: Operand::Constant(func),  .. }</code>, then do some initial heuristics for number of arguments in a function, and at the end match <code>func.literal</code> as <code>ty::Const{ty, val}</code> with <code>ty.kind()</code> being <code>ty::FnDef(def_id, substs)</code>. So as far as I understand there should be some way to use <code>def_id</code> and find what this function is, but I didn't find it</p>



<a name="242861156"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242861156" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242861156">(Jun 16 2021 at 10:27)</a>:</h4>
<p>right, my "plan" would get you the def_id so you can "== compare"  the def ids to see if you have the right one. If you want to start from the DefId, you gotta check the name via <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.item_name">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.item_name</a> to see if it is "len", and then <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.impl_of_method">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/ty/context/struct.TyCtxt.html#method.impl_of_method</a> to get the impl block's id. Then you compare that id with <a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/lang_items/struct.LanguageItems.html#method.slice_impl">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_hir/lang_items/struct.LanguageItems.html#method.slice_impl</a> to see whether you got the correct slice impl block</p>



<a name="242861570"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242861570" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242861570">(Jun 16 2021 at 10:32)</a>:</h4>
<p>Ok, I see. Most likely your way is actually better, now I just need to get <code>LanguageItems</code> from somewhere to prefetch the ID :)</p>



<a name="242861911"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242861911" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242861911">(Jun 16 2021 at 10:35)</a>:</h4>
<p><a href="https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/?search=LanguageItems">https://doc.rust-lang.org/nightly/nightly-rustc/rustc_middle/?search=LanguageItems</a></p>



<a name="242861921"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242861921" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242861921">(Jun 16 2021 at 10:35)</a>:</h4>
<p>rustdoc at your service <span aria-label="wink" class="emoji emoji-1f609" role="img" title="wink">:wink:</span></p>



<a name="242862326"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242862326" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242862326">(Jun 16 2021 at 10:39)</a>:</h4>
<p>I've meant "how to get known LanguateItems" and not what they are inside, but found it already</p>



<a name="242868073"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242868073" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242868073">(Jun 16 2021 at 11:41)</a>:</h4>
<p>oh, the rustdoc link didn't link there</p>



<a name="242868074"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242868074" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242868074">(Jun 16 2021 at 11:41)</a>:</h4>
<p>sorry</p>



<a name="242868128"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242868128" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242868128">(Jun 16 2021 at 11:42)</a>:</h4>
<p>you can click "in return types" to see functions returning what you searched</p>



<a name="242871768"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242871768" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242871768">(Jun 16 2021 at 12:19)</a>:</h4>
<p>As for the dataflow analysis: I didn’t yet get a good idea how it works. I assume it allows me to follow the chains like _4 = Len(*2), _6 = _4, but doesn’t look easily so</p>



<a name="242875742"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242875742" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242875742">(Jun 16 2021 at 12:56)</a>:</h4>
<p>Is it potentially acceptable to use salsa in MIR? It looks as a good query engine implementation with caching</p>



<a name="242876907"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242876907" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Jonas Schievink  [he/him] <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242876907">(Jun 16 2021 at 13:06)</a>:</h4>
<p>the compiler already has a query system</p>



<a name="242877437"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242877437" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242877437">(Jun 16 2021 at 13:10)</a>:</h4>
<p>For range analysis the problem is simpler than constant evaluation, but it requires multiple passes anyway when we can first identify and make first guesses about the range and later improve the precision. I thought salsa would naturally fit here, but have to idea on how compiler query system can be utilized or extended here</p>



<a name="242889057"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242889057" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242889057">(Jun 16 2021 at 14:30)</a>:</h4>
<p><span class="user-mention silent" data-user-id="420832">Alex Vlasov</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Different.20access.20to.20slice.20length/near/242877437">said</a>:</p>
<blockquote>
<p>For range analysis the problem is simpler than constant evaluation, but it requires multiple passes anyway when we can first identify and make first guesses about the range and later improve the precision. I thought salsa would naturally fit here, but have to idea on how compiler query system can be utilized or extended here</p>
</blockquote>
<p>this is what dataflow allows you to do. It runs through your control flow graph and figures out your invariants on the fly, even handling loops. It is used for asking things like "is this local variable potentially alive at this point?" or "is this local variable guaranteed alive at this point?" or in clippy: "is this clone unnecessary because the original value is never used again after the clone?". So in your case you would not have a binary thing, but you'd be building the range that a local variable's value has at each point.</p>



<a name="242890745"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242890745" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242890745">(Jun 16 2021 at 14:42)</a>:</h4>
<p>Ok, I'll try to look deeper into the dataflow. I want to start small with being able from the statement like</p>
<div class="codehilite"><pre><span></span><code>          _5 = core::slice::&lt;impl [u8]&gt;::len(move _6)
</code></pre></div>
<p>to find the last place of definition of _6 like</p>
<div class="codehilite"><pre><span></span><code>          _6 = &amp;(*_2);
</code></pre></div>
<p>instead of doing it manually</p>



<a name="242896463"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242896463" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242896463">(Jun 16 2021 at 15:21)</a>:</h4>
<p>hmm</p>



<a name="242896759"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242896759" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242896759">(Jun 16 2021 at 15:23)</a>:</h4>
<p>we do have a peephole opt to get rid of reborrows I think, maybe just run your optimization after that? and possibly even after nrvo</p>



<a name="242900246"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242900246" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242900246">(Jun 16 2021 at 15:48)</a>:</h4>
<p>Looks like I need to do it before inlining, otherwise bodies are inlined and I may need to make another kind of search for it</p>



<a name="242916010"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242916010" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242916010">(Jun 16 2021 at 17:41)</a>:</h4>
<p>I've tried to fit it before inlining + do <code>mir-opt-level=3</code>, but passes didn't provide any substitutions for equivalents. Here is a full listing</p>
<div class="codehilite"><pre><span></span><code>// MIR for `bound` after SimplifyLocals

fn bound(_1: usize, _2: &amp;[u8]) -&gt; u8 {
    debug index =&gt; _1;                   // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:26:14: 26:19
    debug slice =&gt; _2;                   // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:26:28: 26:33
    let mut _0: u8;                      // return place in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:26:45: 26:47
    let mut _3: bool;                    // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:27
    let mut _4: usize;                   // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:13
    let mut _5: usize;                   // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:16: 27:27
    let _6: usize;                       // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:15: 28:20
    let mut _7: usize;                   // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21
    let mut _8: bool;                    // in scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21

    bb0: {
        StorageLive(_3);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:27
        StorageLive(_4);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:13
        _4 = _1;                         // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:13
        StorageLive(_5);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:16: 27:27
        _5 = Len((*_2));                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:16: 27:27
        _3 = Lt(move _4, move _5);       // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:8: 27:27
        StorageDead(_5);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:26: 27:27
        StorageDead(_4);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:26: 27:27
        switchInt(move _3) -&gt; [false: bb2, otherwise: bb1]; // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:5: 31:6
    }

    bb1: {
        StorageLive(_6);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:15: 28:20
        _6 = _1;                         // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:15: 28:20
        _7 = Len((*_2));                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21
        _8 = Lt(_6, _7);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21
        assert(move _8, &quot;index out of bounds: the length is {} but the index is {}&quot;, move _7, _6) -&gt; bb3; // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21
    }

    bb2: {
        _0 = const 42_u8;                // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:30:9: 30:11
        goto -&gt; bb4;                     // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:5: 31:6
    }

    bb3: {
        _0 = (*_2)[_6];                  // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:28:9: 28:21
        StorageDead(_6);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:29:5: 29:6
        goto -&gt; bb4;                     // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:27:5: 31:6
    }

    bb4: {
        StorageDead(_3);                 // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:31:5: 31:6
        return;                          // scope 0 at /Users/alexvlasov/MatterLabs/rust/src/test/mir-opt/basic_range.rs:32:2: 32:2
    }
}
</code></pre></div>
<p>(This is after last pass of SimplifyLocals)</p>



<a name="242916604"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242916604" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242916604">(Jun 16 2021 at 17:46)</a>:</h4>
<p>May be <code>move</code> is a problem, but </p>
<div class="codehilite"><pre><span></span><code>_3 = Lt(move _4, move _5);
</code></pre></div>
<p>and</p>
<div class="codehilite"><pre><span></span><code>_9 = Lt(_6, _7);
</code></pre></div>
<p>are the same  operations: <code>_4 = _1, _5 = Len((*2))</code> and <code>_6 = _1, _7 = Len((*2))</code>, but no passes have allowed to converge them. </p>
<p>Another interesting thing: I do not see any <code>StorageLive(_7)</code> anywhere...</p>



<a name="242917007"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242917007" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242917007">(Jun 16 2021 at 17:49)</a>:</h4>
<p>I assume if it's ok to have <code>_7 = Len()</code> without <code>StorageLive(_7)</code> then I should also remove it for <code>_5</code> if possible (it's local, and goes Live, move and Dead). May be <code>move</code> is indeed a problem and I have to change some extra info to change properties of <code>_5</code> ?</p>



<a name="242930023"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242930023" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242930023">(Jun 16 2021 at 19:26)</a>:</h4>
<p><span class="user-mention silent" data-user-id="420832">Alex Vlasov</span> <a href="#narrow/stream/189540-t-compiler.2Fwg-mir-opt/topic/Different.20access.20to.20slice.20length/near/242900246">said</a>:</p>
<blockquote>
<p>Looks like I need to do it before inlining, otherwise bodies are inlined and I may need to make another kind of search for it</p>
</blockquote>
<p>right, the len -&gt; Len lowering. I would recommend you open a PR that does just that (and does it in the intrinsic lowering pass), it has a potential perf impact and is generally something I think we want regardless of your other changes (which I also think we want for the record)</p>



<a name="242930140"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242930140" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242930140">(Jun 16 2021 at 19:27)</a>:</h4>
<p>my recommendation would be to convert  <code>_5 = core::slice::&lt;impl [u8]&gt;::len(move _6)</code> into <code>_5 = Len(*_6)</code> instead of doing anything complex like figuring out where _6 came from</p>



<a name="242930180"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242930180" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242930180">(Jun 16 2021 at 19:28)</a>:</h4>
<p>and then let the other optimizations take their course</p>



<a name="242930309"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242930309" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242930309">(Jun 16 2021 at 19:28)</a>:</h4>
<p>then look at the MIR at different optimizations situations and look if another optimization can be helpful to get the code into a pattern that is useful for figuring out that we're doing a length check twice</p>



<a name="242930744"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242930744" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242930744">(Jun 16 2021 at 19:32)</a>:</h4>
<p>Storage markers are odd, yes. Technically we don't need live markers and can compute them on the fly anyway</p>



<a name="242931091"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242931091" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> oli <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242931091">(Jun 16 2021 at 19:34)</a>:</h4>
<blockquote>
<p>are the same operations: _4 = _1, _5 = Len((<em>2)) and _6 = _1, _7 = Len((</em>2)), but no passes have allowed to converge them. </p>
</blockquote>
<p>that sounds like a good candidate for a peephole opt. If we can find duplicate rvalues, we can just reuse the previously computed value if its local is at least as live as the one of the second computation</p>



<a name="242949279"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242949279" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242949279">(Jun 16 2021 at 22:05)</a>:</h4>
<p><a href="https://github.com/rust-lang/rust/pull/86383">https://github.com/rust-lang/rust/pull/86383</a></p>



<a name="242950633"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242950633" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242950633">(Jun 16 2021 at 22:20)</a>:</h4>
<p>(I kicked CI on it)</p>



<a name="242950906"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242950906" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> krdln <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242950906">(Jun 16 2021 at 22:23)</a>:</h4>
<p>(small offtop) <span class="user-mention" data-user-id="420832">@Alex Vlasov</span> I just wanted to chime in and say that your PR is a beautiful teaching example for the MIR optimizations (and in addition, it, of course is usable!). I've stumbled on this thread, read the code top-to-bottom and (knowing nothing more about MIR than the idea) basically understood it all. The little comments you've added were also in _just_ right amount, helpful, not overwhelming. Thank you! (you and everyone in this thread ofc :))</p>



<a name="242952134"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242952134" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Alex Vlasov <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242952134">(Jun 16 2021 at 22:37)</a>:</h4>
<p>Thank you for a feedback, <span class="user-mention" data-user-id="125261">@krdln</span></p>



<a name="242977115"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/189540-t-compiler/wg-mir-opt/topic/Different%20access%20to%20slice%20length/near/242977115" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> Théo Degioanni <a href="https://rust-lang.github.io/zulip_archive/stream/189540-t-compiler/wg-mir-opt/topic/Different.20access.20to.20slice.20length.html#242977115">(Jun 17 2021 at 06:17)</a>:</h4>
<p>(deleted)</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>